#ifndef CONVEX_HULL_H_
#define CONVEX_HULL_H_

#include <vector>
#include "geometry.h"

bool operator == (const Point& a, const Point& b)
{
   return ((a.x == b.x) && (a.y == b.y));
}

bool operator != (const Point& a, const Point& b)
{
   return !(a == b);
}

class polar_comparator
{
private:
   Point p0;

public:
   bool operator() (Point& a, Point& b)
   {
      if((b == p0) || (a == b) && (a == p0))
         return false;
      if(a == p0)
         return true;
      int lt = left_turn(p0, a, b);
      return lt > 0 || (lt == 0) && ((a.y < b.y) || (a.y == b.y) && (a.x < b.x));
   }

   polar_comparator(Point p0_): p0(p0_)
   {  };

};
std::vector<Point> convex_hull(std::vector<Point>& point_list)
{
   std::vector<int> res;
   res.push_back(0);
   if (point_list.size() < 2)
      return point_list;   
   res.push_back(1);

   for (int i = 2; i < point_list.size(); i++)
   {
      while ((res.size() >= 2) && (left_turn(point_list[res.size() - 2], point_list[res.size() - 1],  point_list[i]) < 0))
         res.pop_back();
      res.push_back(i);
   }

   if(res.size() == 2 && res[0] == res[1])
      res.pop_back();

   std::vector<Point> ans;
   for (int i = 0; i < res.size(); i++)
      ans.push_back(point_list[res[i]]);

   return ans;
}
#endif